#pragma once
#include "router.h"

//////////////////////////////////////////////////////////////////////////
//- Custom Types
//////////////////////////////////////////////////////////////////////////
struct tPos 
{
	int x,y;

	tPos();

	void assign(int x0, int y0);
	void reset();
	bool operator==(const tPos &v);

	bool operator!=(const tPos &v);
};


struct tSolution
{
	float cost;
	string track;
};
struct tNode
{
	tPos state, parent;
	char action;
	float cost;
	int t;
	bool isSolution;

	tNode();

	void reset();

	bool operator==(const tNode &v);

	bool operator!=(const tNode &v);
};


//////////////////////////////////////////////////////////////////////////
//- Main Class
//////////////////////////////////////////////////////////////////////////

class DepthFirstRouter :
	public Router
{
public:
	DepthFirstRouter(void);
	~DepthFirstRouter(void);

	std::vector<iPos> route(std::vector< std::vector< char >> map, fPos nowPos, iPos targetPos);

	int MapW, MapH;
	tPos StartC, EndC, StartP;
	priority_queue<tNode, vector<tNode>, greater<vector<tNode>::value_type> > OpenSet;
	multimap<int, tNode>						ClosedSet;
	vector<tPos> TrackPosC;

	multimap<int, tNode>::iterator 
		find_state_in_closed(tNode &node)
	{
		multimap<int, tNode>::iterator itr;

		itr = ClosedSet.find(node.state.x);
		for(; (itr!=ClosedSet.end())&&(node.state.x == itr->second.state.x); itr++)
		{
			if((node.state == itr->second.state))
				return itr;
		}

		return ClosedSet.end();
	}

private:
	
};
